# 剑指 Offer 38. 字符串的排列
def main(s):
    # 回溯法
    s, res, tmp = list(s), list(), list()
    s.sort()

    def dfs(s):
        if len(s) == 0:
            res.append(''.join(tmp))
            return
        for i, c in enumerate(s):
            if i > 0 and s[i] == s[i - 1]:  # 剪枝，同一个dfs(s)中，相同的字符不需要重复计算
                continue
            s.pop(i)

            tmp.append(c)
            dfs(s)
            s.insert(i, c)
            tmp.pop(-1)
        pass

    dfs(s)
    # print(len(res))
    return res


if __name__ == '__main__':
     print(main("acxxxc"))
